package main

import (
	"fmt"
	"math/rand"
	"log"
)
func main(){
	// 随机生成测试用例
	arr := make([]int, 100)
	for i := 0; i < len(arr); i++ {
		arr[i] = int(rand.Int31n(100))
		fmt.Printf("%d ",arr[i])
	}
	QuicklySort(arr)
	fmt.Print(arr)
}

func QuicklySort(arr []int) {
	if len(arr) <= 1 {
		log.Printf("Array length is %d, no need to sort.", len(arr))
		return
	}

	pivotIndex := 0
	left := 1
	right := len(arr) - 1

	for left < right {
		// 先移动right
		for left < right && arr[right] >= arr[pivotIndex] {
			right--
		}
		// 后移动left
		for left < right && arr[left] <= arr[pivotIndex] {
			left++
		}
		if left < right {
			arr[left], arr[right] = arr[right], arr[left]
		}
	}

	// 如果left == right，则left或right都指向pivot，此时将pivot与left或right交换，即可将pivot放到正确位置
	if arr[left] < arr[pivotIndex] {
		arr[left], arr[pivotIndex] = arr[pivotIndex], arr[left]
		pivotIndex = left
	}

	if pivotIndex > 0 {
		QuicklySort(arr[:pivotIndex])
	}
	if pivotIndex < len(arr)-1 {
		QuicklySort(arr[pivotIndex+1:])
	}
}